import collections


class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.end = collections.defaultdict(dict)


class Solution(object):
    def wordsAbbreviation(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        n = len(words)
        root = Node('#')

        def search(node, id_set, j):
            for id in id_set:
                k = len(words[id])
                if words[id][j] not in node.neighbors:
                    next_node = Node(words[id][j])
                    next_node.end[words[id][-1]][k - j - 2] = id
                    node.neighbors[words[id][j]] = next_node
                else:
                    next_node = node.neighbors[words[id][j]]
                    if k - 2 - j in next_node.end[words[id][-1]]:
                        next_set = {id}
                        if next_node.end[words[id][-1]][k - 2 - j] >= 0:
                            next_set.add(next_node.end[words[id][-1]][k - 2 - j])
                        next_node.end[words[id][-1]][k - 2 - j] = -1
                        search(next_node, next_set, j + 1)
                    else:
                        next_node.end[words[id][-1]][k - 2 - j] = id

        for i in range(len(words)):
            node = root
            if len(words[i]) == 1:
                root.end[words[i][0]][-1] = 0
            else:
                search(node, {i}, 0)

        def find(s, node):
            if node == root:
                for key in node.end:
                    words[node.end[key][-1]] = key
            else:
                for key in node.end:
                    for l in node.end[key]:
                        if l > 1 and node.end[key][l] >= 0:
                            words[node.end[key][l]] = s + str(l) + key
            for key in node.neighbors:
                find(s + key, node.neighbors[key])

        find('', root)
        return words


data = Solution()
words = ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
print(data.wordsAbbreviation(words))
words = ["abcdefg", "abccefg", "abcckkg"]
print(data.wordsAbbreviation(words))
